Generally, computer graphics systems represent dynamic images by displaying data on the screen of a cathode ray tube (CRT). Typically, the CRT screen displays a rectangular array of thousands of individual picture elements (pixels). To activate displays, the visual characteristic such as the color, intensity and depth of each pixel is defined by associated pixel data.
In traditional three-dimensional graphics systems, three-dimensional images (containing a variety of objects or primitives) are generated for representation on the two-dimensional CRT screen. The operation involves defining a three-dimensional model space (e.g., a frustum of vision from a predefined viewpoint) and assigning sections of the model space (called component pixel frustums) to the pixels of the CRT screen. During a process known as polygon rendering, the pixel data is calculated according to the characteristics of objects or primitives, e.g., three-dimensional polygons, that lie in that pixel's frustum. The degree to which a given polygon is displayed by a given pixel depends on the intersection of the pixel's frustum with the polygon. The intersection defines an area, called a projected pixel footprint, on the polygon. Accordingly, each pixel displays the combined visual effects such as color, shade and transparency defined within the projected pixel footprint on all the polygons in that pixel's frustum.
The visual characteristics of a polygon may be enhanced by texturing the polygon. Texture is analogous to a digital wallpaper that is applied to surfaces, e.g., polygons. Texture can represent changes in any spatially varying surface parameter and is typically used to represent changes in intensity, color, opacity, or thematic content (such as surface material type). The process of applying texture patterns to surfaces is generally referred to as "texture mapping" and is a well known and widely used technique in computer graphics. For example, see U.S. Pat. No. 4,855,943 (System For Texturing Computer Graphics Images, Robinson) and the textbook Computer Graphics: Principles and Practice., 2nd Edition, Foley, van Dam, Feiner & Hughes, (Reprinted in 1991)(1990), by Addison-Wesley Publishing Company, at section 16.3.2.
Texture is an implicitly regular two-dimensional array of data. Data elements in the array are called texels and the array is called a texture map. The texture coordinate space is implied by the nature of the array, i.e., its two coordinate axes are defined by the rows and columns of the array typically designated in "u" and "v" coordinates. Thus, the arrangement and scaling of the array has spatial and visual meaning.
A texture map is applied (mapped) to surfaces by designating the relationship of the texture coordinate space to the polygon coordinate space. Then, during the polygon rendering process, the texture data is combined with the other attributes of the polygon to determine the final pixel data values.
In the three-dimensional model space, texels undergo the same perspective distortions as the polygon. Consequently, when a polygon is rendered, range, angle or perspective may, for example, cause the squares of a texture checkerboard to become smaller than the projected pixel footprint. If either dimension of the texel becomes smaller than the pixel footprint and some texels are occasionally skipped over in the rendering process, the intermittent inclusion of texels can cause aliasing of the texture in the displayed pixels. This can happen even if the perspective texels are larger than the pixel footprint in one dimension. That is, the aliasing occurs based on the smaller dimension of the perspective texel.
Aliasing is a well known term applied to a wide variety of image quality problems. The term refers to high frequency image content masquerading as low frequency content. The visual effects of aliasing include image crawling, edge stair casing, scintillation, moire patterns and general image noise.
Texture mapping has some characteristics that exacerbate the anti-aliasing issue. As seen by a viewer, most texture has been perspectively compressed in one dimension more than in the other dimension. This is because many polygon surfaces are defined at an oblique angle to the viewer. As polygon surfaces tilt to become more and more oblique to the viewer, the footprint of the pixel frustum on the polygon becomes progressively stretched and distorted into a long quadrilateral with a high aspect ratio. When this happens, more texels will be within the footprint along the length of the footprint than across the width of the footprint. If the texels along the length of the footprint are not adequately sampled, aliasing may occur.
One method of preventing texture aliasing on oblique polygons involves retrieving the texel values of all the texels within the pixel footprint and filtering or averaging all the texel values. However, since the size of the frustum grows as the distance from the viewer increases, this approach becomes computationally intractable because huge numbers of texels can be within the footprint.
To reduce the amount of processing required, some methods use a technique known as MIP mapping. MIP mapping and the use of MIP maps for texture mapping is treated in a paper entitled "Pyramidal Parametrics" by Lance Williams, published July 1983 in Computer Graphics, volume 17, no. 3. The article has been identified by the Association For Computing Machinery as ACM 0-89791-109-1/83/007/0001.
The MIP mapping technique uses a texture map that has a succession of different levels of detail. Each successive level of detail covers the same portion of the polygon with half as many texels in each direction. Thus, each successive level of detail has one fourth as many total texels as the previous level. Since the mapping between the polygon and the map does not change, the texels are, in effect, larger in each successive level. During rendering, the appropriate texture level of detail is selected (usually by interpolation) based on the relationship of texel size to pixel size. Thus, MIP mapping works by ensuring that, at the displayed texture level of detail, every texel is at least as big as the pixel that is associated with that texel. Using the MIP mapping approach, no texels are skipped over during the sampling process.
Current systems use the long dimension of the projected pixel footprint to determine the MIP map level of detail to ensure that only a single texture look-up is required for each pixel. Thus, the texels appear one pixel high along the length of the footprint. However, since the texels are square, they will appear to be many pixels wide across the width of the footprint. In this situation, the texture fully modulates the pixels along the length of the footprint and hardly modulates the pixels at all across the width of the footprint. This leads to a peculiar visual effect where textural details seem to attenuate very rapidly on oblique surfaces.
Several polygon mapping techniques are discussed in the above-referenced textbook Computer Graphics: Principles and Practice, at section 17.4.3. A number of these techniques involve precomputing lower texture levels of detail with non-square filter kernels. In effect, these solutions average rectangles of texels rather than squares of texels to create new levels of detail. The most aggressive of these approaches is the "sum-table" texture method where the average of any arbitrary rectangle of texels is determined from several look-ups. All of these approaches are lacking because the projected pixel footprint on oblique polygons is not only stretched, but can fall across the texture space at any orientation. Thus, the footprint does not conveniently align with the texture axis. Consequently, using rectangles of averaged texels does not provide a desirable solution.
An elliptical weighted average scheme provides good results, but is not architecturally tractable in a system that must solve pixels at high continuous rates since this scheme requires a large indeterminate number of texture look-ups within each pixel. Consequently, a need exists for an improved computer graphics system that can display oblique texture mapped polygons with minimal aliasing and minimal loss of detail but without exceedingly high processing loads.
The present invention uses a combination of MIP mapping and supersampling to reduce aliasing of texture on an oblique polygon. This technique is based on recognizing that the desired texture level of detail is the level where the size of the texels is equal to the width of the projected pixel footprint not the length of the footprint. By using this level of detail, good modulation across the width of the footprint is obtained.
To reduce aliasing along the length of the pixel footprint, the texture defined within the footprint is supersampled (i.e., multiple texture samples are taken). Specifically, texture samples are taken from the MIP map at locations corresponding to sample points within the footprint along the length of the footprint. These samples are blended to create a single texture value which is blended with the other pixel information to form the final pixel value.
The present invention provides a simple, real-time method of effectively controlling the extra processing load that is required to supersample the texture data. Since the determination of whether to supersample is made on a pixel-by-pixel basis, only those portions of the scene needing supersampling cost extra processing. Thus, only oblique textured polygons will be supersampled and relatively little extra processing will be used when non-oblique polygons are rendered. The process will determine how many samples are to be taken based on a number of factors including the aspect ratio of the projected pixel footprint. In addition, the number of supersamples can be limited to a predefined maximum, thereby reducing the number of samples taken from high aspect ratio footprints.
In a preferred embodiment, a MIP map level of detail is chosen so that the width of the texels from the MIP map approximate the width of the projected pixel footprint. If the length of the footprint is greater than the width, multiple sample points are defined along the length of the footprint. These sample points are defined at spaced intervals along a straight line in the center of the pixel footprint. The sample points defined within the projected pixel footprint are then mapped to the appropriate level of detail in the MIP map whereupon the locations in the MIP map that correspond to the sample points are read. These samples are blended together giving equal weight to each sample, i.e., the sampled values are simply averaged, to form the texture information for the pixel.
The present invention thus utilizes the efficiency of the MIP mapping technique while providing greater texture detail when displaying polygons defined at oblique angles. In addition, relatively simple real time controls are provided that control the amount of extra processing needed to supersample the texture data.